#include <iostream>

// A generic function pointer for comparison
typedef int (*CPF) (const void*, const void*);

int cmp_int(const void* p, const void* q)
{
  return *(static_cast<const int*>(p)) - *(static_cast<const int*>(q));
}


double cmp_double(const void* p, const void* q)
{
  return *(static_cast<const double*>(p)) - *(static_cast<const double*>(q));
}


void
qsort(void* base, std::size_t left, std::size_t right, std::size_t sz, CPF cmp)
{
  if (right > left)
    {
      std::size_t leftIdx = left;
      std::size_t rightIdx = right;
      std::size_t pivot = (left + right) / 2;
      char* b = static_cast<char*>(base);

      do
	{
	  char* pleft = b + leftIdx*sz;
	  char* pp = b + pivot*sz;

	  while (cmp(pleft, pp) < 0)
	    {
	      ++leftIdx;
	      pleft += sz;
	    }

	  char* pright = b + rightIdx*sz;
	  while (cmp(pp, pright) < 0)
	    {
	      --rightIdx;
	      pright -= sz;
	    }

	  if (leftIdx <= rightIdx)
	    {
	      // swap base[leftIdx], base[rightIdx]
	      for (int k = 0; k < sz; ++k)
		{
		  char temp = pleft[k];
		  pleft[k] = pright[k];
		  pright[k] = temp;
		}
	      ++leftIdx;
	      --rightIdx;
	    }
	}
      while (leftIdx <= rightIdx);

      if (left < rightIdx) qsort(base, left, rightIdx, sz, cmp);
      if (leftIdx < right) qsort(base, leftIdx, right, sz, cmp);
    }
}

int
main()
{
  int i = 3;
  int j = 4;

  int* pi = &i;
  int* qi = &j;

  std::cerr << "cmp_int(3, 4): " << cmp_int(pi, qi) << std::endl;
  
  double d = 2.5;
  double e = 1.8;

  double* pd = &d;
  double* qd = &e;

  std::cerr << "cmp_double(2.5, 1.8): " << cmp_double(pd, qd) << std::endl;

  int v[10] = {3, 1, 5, 4, 9, 0, 6, 8, 7, 2};
  qsort(v, 10, sizeof(int), cmp_int);

  for (int i = 0; i < 10; ++i)
    std::cerr << v[i] << " ";
  std::cerr << std::endl;
}
